Video coding is used in a wide range of multimedia applications including digital television, videoconferencing, mobile video and video streaming. Video coding has developed with a number of international standards. A number of these international standards include the use of variable length codes (VLCs). For example, in the international standard jointly published by the ITU-T as Recommendation H.263+, a variable length code (VLC) decoding is included.
In the prior art, some variable length code (VLC) decoding implementations use lookup tables (LUTs). For example, a H.263+decoder of Intel Corporation of Santa Clara, Calif., used LUTs to decode VLC codes. However, this decoder only used the LUTs to decode coefficients and zero run information. These LUTs were readily generated from the tables in the H.263+standard's specification. The current draft of the H.264/MPEG-4 Part 10 specification includes a decoding process in which VLC codes are used. See “Draft Errata List with Revision-Marked Corrections for H.264/AVC, the approved JVT output document from the Sep. 2-5, 2003 meeting, JVT-I050.doc. In common with earlier video coding standards, H.264 does not specify how to compress (“encode”) video and, instead, specifies the syntax of a bitstream containing coded video data and a method of decoding the data.
During entropy coding with an H.264 video encoder, quantized transform coefficients and side information (including motion vectors, prediction mode choices and headers) are entropy coded using variable-length codes or arithmetic coding. If variable-length coding is used, quantized transform coefficients are coded using a context-adaptive variable length coding (CAVLC) and other syntax elements are coded with “universal” variable length codes.
CAVLC exploits the coefficients' statistical correlation by first scanning them in a zigzag manner into a one-dimensional array. Every non-zero coefficient is then associated with a variable run that counts the number of zero coefficients to the previous non-zero coefficient.
Often 1 bits with a sign are among the highest-frequency coefficients. These are counted and coded with the total number of non-zero coefficients using one rule from a set of code tables. The decision of which table to use is made based on the number of non-zero coefficients in neighboring blocks. Additionally, the sign of the 1 bits has to be indicated to the decoder. The values of the remaining coefficients are then coded using adaptive Rice codes. Thus, several code tables are used, and the choice among the tables is made according to the value of the previously encoded coefficient. Thereafter, the sum of the runs is computed and encoded with one out of 15 tables depending upon the number of non-zero coefficients in that block. At this point, the only remaining operation is to code the individual run values with one out of seven code tables, depending upon the remaining sum of the runs. All code tables used by CAVLC are generated empirically.
To summarize, CAVLC encoding of a block of transform coefficients proceeds as follows. First, the number of coefficients and trailing ones (T1s) are encoded. Second, the sign of each T1 is encoded. Next, the levels of the remaining non-zero coefficients are encoded. Then, the total number of zeros occurring before the last coefficient is encoded. Lastly, each run of zeros is encoded.
An H.264 reference software implementation is currently available. The software implementation uses pattern-matching to obtain the number of coefficients and the number of trailing ones. In this software implementation, pattern matching is used between the codes in an encoder lookup table (LUT) and the bits at the head of the bitstream. Other implementations use LUTs to obtain the number of coefficients and the number of trailing ones. However, because of the size of the tables is large in order to accommodate all of the possible inputs, the use of these tables is not efficient and is slow. Similarly, LUTs are used in prior art implementations to obtain the number of total zeros, and have the same limitations as those implementations to obtain the number of coefficients and the number of trailing ones.